package com.code.test.second.dp;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.md
 * <p>
 * 746. 使用最小花费爬楼梯
 * 力扣题目链接
 * <p>
 * 旧题目描述：
 * <p>
 * 数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
 * <p>
 * 每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
 * <p>
 * 请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
 * <p>
 * 示例 1：
 * <p>
 * 输入：cost = [10, 15, 20]
 * 输出：15
 * 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
 * 示例 2：
 * <p>
 * 输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
 * 输出：6
 * 解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。
 * 提示：
 * <p>
 * cost 的长度范围是 [2, 1000]。
 * cost[i] 将会是一个整型数据，范围为 [0, 999] 。
 */
public class SCode746 {

    public static void main(String[] args) {
        int[] cost = {10, 15, 20};
        int ret = fib3(cost);
        System.out.println(ret);
    }

    private static int fib3(int[] cost) {

        /**
         * 题目写着是从当前台阶，花费体力值后，可以选择爬一阶或者2阶
         * 1、dp[i] 代表 到达下标 为i的台阶所需要花费的最小体力值是多少
         * 2、dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
         * 为什么是这个，站在dp[i-1]台阶不花费，向上要花费当前台阶的体力值，同理cost[i-2]
         * 所以dp[i-1]+cost[i-1]代表在i-1阶花费cost[i-1]可以跳到dp[i]阶,向上跳一格
         * 所以dp[i-2]+cost[i-2]代表在i-2阶花费cost[i-2]可以跳到dp[i]阶，向上跳2格
         * 3、dp[0]=1 dp[1]=1
         * 4、递推
         * 5、打印
         */

        /**
         * 因为i从1开始，所以1...n,数组有n个元素
         */
        int n = cost.length;
        int[] dp = new int[n+1];

        //站在第一阶不花费
        dp[0] = 0;
        //站在第二阶不花费
        dp[1] = 0;
        //因为要遍历到n

        /**
         * 这里之所以是n，
         * i=0 代表第一阶，对应0 花费
         * i=1 代表第二阶，对应0 花费
         * i=2 代表第三节，对应i=0或i=1的花费,
         * cost[n] = [10,15,20];这里n-1=20这里不是最上面，还要再上一个，所以i<=n
         * cost是花费，而台阶是要花完之后再上台阶，所以是i<=n
         *
         * dp[i-1]+cost[i-1] 代表站在i-1台阶，要花费cost[i-1]，目标是上到dp[i]这一阶
         */
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
}
